package com.xmg.leetCode;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 * 思路：遍历每个字符，然后向两边扩散，注意分两种情况  aba和abba
 */
public class No5 {
    public static void main(String[] args) {
        System.out.println(Solution5.longestPalindrome("cbbd"));
    }
}
class Solution5 {

    public static String longestPalindrome(String s) {
        if(s.length()<2){
            return s;
        }
        int start = 0;
        int maxLength = 1;
        int left,right;
        for (int i = 0; i < s.length(); i++) {
//            expand(i-1,i+1,s);
//            expand(i,i+1,s);
            left = i-1;
            right = i+1;
            while (left>=0 && right < s.length() && s.charAt(left)==s.charAt(right)){
                if(right-left+1>maxLength){
                    maxLength = right-left+1;
                    start = left;
                }
                left--;
                right++;
            }
            left = i;
            right = i+1;
            while (left>=0 && right < s.length() && s.charAt(left)==s.charAt(right)){
                if(right-left+1>maxLength){
                    maxLength = right-left+1;
                    start = left;
                }
                left--;
                right++;
            }
        }
       return s.substring(start,start+maxLength);

    }

//    public static void expand(int left , int right,String s){
//        while (left>=0 && right < s.length() && s.charAt(left)==s.charAt(right)){
//            if(right-left+1>maxLength){
//                maxLength = right-left+1;
//                start = left;
//            }
//            left--;
//            right++;
//        }
//    }
}